class Solution:
	# @param {integer[]} nums1
	# @param {integer[]} nums2
	# @return {float}
	def findMedianSortedArrays(self, nums1, nums2):
		if len(nums1) >= len(nums2):
			return self.findMedian(nums1, nums2, 0, len(nums1), 0, len(nums2))
		else:
			return self.findMedian(nums2, nums1, 0, len(nums2), 0, len(nums1))

	def findMedian(self, nums1, nums2, n1_start, n1_end, n2_start, n2_end):
		# nums1 no smaller than nums2
		size1 = n1_end - n1_start
		size2 = n2_end - n2_start
		if size1 == 0:
			return None
		if size2 == 0:
			if size1 % 2 == 0:
				return (nums1[size1/2-1] + nums1[size1/2])/2.0
			else:
				return nums1[size1/2]
		even1 = bool(size1 % 2 == 0)
		even2 = bool(size2 % 2 == 0)
		mid1 = mid2 = 0
		if even1:
			mid1 = (nums1[n1_start+size1/2-1]+nums1[n1_start+size1/2]) / 2.0
		else:
			mid1 = nums1[n1_start+size1/2]
		if even2:
			mid2 = (nums2[n2_start+size2/2-1]+nums2[n2_start+size2/2]) / 2.0
		else:
			mid2 = nums2[n2_start+size2/2]
		if size2 <= 2:
			x, y = n1_start, n2_start
			c, m = 0, (size1+size2)/2+1
			f = t = 0
			while x < n1_end and y < n2_end:
				if c == m:
					return f if (size1+size2) % 2 == 1 else (f+t)/2.0
				else:
					if nums1[x] <= nums2[y]:
						t = f
						f = nums1[x]
						x += 1
					else:
						t = f
						f = nums2[y]
						y += 1
					c += 1
			print (x,y)
			if x == n1_end:
				for i in xrange(m-c):
					t = f
					f = nums2[y+i]
				return f if (size1+size2) % 2 == 1 else (f+t)/2.0
			else:
				for i in xrange(m-c):
					t = f
					f = nums1[x+i]
				return f if (size1+size2) % 2 == 1 else (f+t)/2.0


		if mid1 == mid2:
			return mid1
		elif mid1 < mid2:
			cutting_size = size2 / 2 - (1 if even2 else 0)
			t1_start = n1_start + cutting_size
			t1_end = n1_end
			t2_start = n2_start
			t2_end = n2_end - cutting_size
		else:
			cutting_size = size2 / 2 - (1 if even2 else 0)
			t1_start = n1_start
			t1_end = n1_end - cutting_size
			t2_start = n2_start + cutting_size
			t2_end = n2_end
		return self.findMedian(nums1, nums2, t1_start, t1_end, t2_start, t2_end)

if __name__ == '__main__':
	n1 = []
	n2 = []
	print Solution().findMedianSortedArrays(n1, n2)



